#include <stdio.h>
#include <string.h>
int main()
{
	int t,count=0;
	scanf("%d",&t);
	while(t!=0)
	{
		int num[20]={0},head=0,tail=0,top=0;
		char str[40]={0};
		int in_count=0;
		scanf("%d",&count);
		scanf("%s",str);
		if(strcmp(str,"FIFO")==0)
		{
			while(count!=0)
			{
				char str1[40]={0};
				scanf("%s",str1);
				if(strcmp(str1,"IN")==0)
				{
					scanf("%d",&num[tail++]);
					in_count++;	
				}
				else 
				{
					if(in_count!=0)
					{
						printf("%d\n",num[head++]);
						in_count--;
					}
					else
				 	printf("None\n");
				}
				count--;
			}
		}
		else
		{
			while(count!=0)
			{
				char str2[40]={0}; 
				scanf("%s",str2);
				if(strcmp(str2,"IN")==0)
				{
					scanf("%d",&num[top++]);
					in_count++;
				}
				else
				{
					if(in_count!=0)
					{
						printf("%d\n",num[--top]);
						in_count--;
					}
					else
					printf("None\n");
				}
				count--;
			}
		}
		t--;
	}
	return 0;
}
